Valya was tired of
social networks and decided to write a letter to her friend Sasha on a
rectangular sheet of paper. The lengths of the sides of the sheet are equal to n
and m centimeters. Then she found a rectangular envelope with side
lengths equal to h and w centimeters.
Unfortunately, the
letter may not fit into the envelope, in this case Valya have
to fold the letter several times. In one action, Valya can fold the
letter in half vertically or horizontally.
After Valya, if necessary,
folds the letter in half several times, she plans to put it into the envelope.
Valya is a very neat girl, she always puts a letter in an envelope so that its
sides are parallel to the sides of the envelope. A letter is placed in an
envelope if its sides are not longer than the corresponding sides of the
envelope. Before putting the letter into the envelope, Valya can rotate it 90 degrees.
For example, if the lengths of the sides of the letter are 10 and 20 centimeters,
and the lengths of the sides of the envelope are 20 and 10 centimeters, Valya
does not need to fold the letter, she can rotate it 90 degrees and put into an
envelope.
Valya does not want
the letter to be very wrinkled, so she wants to fold the letter in half the
minimum number of times. Help her figure out the minimum number of times she has to fold the letter before she can put it in the
envelope.
Input. The first line
contains four integers n, m, h and w (1 ≤ n, m, h, w ≤
1018), the lengths of the sides of the letter and envelope, respectively.
Output. Print one number,
the minimum number of times Valya has to fold the
letter so that she can put it into the envelope.
|
Sample input 1 |
Sample output 1 |
|
10 20 20 10 |
0 |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
3 3 2 2 |
2 |
recursion
First, let’s solve
the problem when the sheet sizes are equal to n and m, and the
envelope sizes are h and w. To do this, we implement the function
solve(n, m, h, w). Then we rotate the
sheet 90 degrees and solve the problem for sheet m * n and
envelope h * w by calling the solve(m, n,
h, w) function. The smallest of these values will be the answer.
Consider the implementation of solve(n, m, h,
w).
· If h ≥ n
and w ≥ m,
then the letter can
be placed in the
envelope and we return 0 (the sheet does not need to be folded);
· If h < n,
then the letter should be folded in half along the side of length n. To
avoid working with real numbers, instead of dividing n by 2 (n /
2 can become real), we’ll
increase the size h of the envelope by 2 times. The number of letter foldings
will become equal to
1
+ solve(n, m, 2 * h, w)
· If w < m increase
the size w of the envelope by 2 times. The number of letter foldings
will become equal to
1
+ solve(n, m, h, 2 * w)
Example
Consider the second test. The number of foldings is
solve(3, 3, 2, 2) = 1
+ solve(3, 3, 4, 2)
= 1 + 1 + solve(3, 3, 4, 4) = 2
The solve(n,
m, h, w) function solves the problem for a sheet with
dimensions n and m, and an envelope with dimensions h and w.
long long solve(long long n, long long m, long long h, long long w)
{
if (h >= n && w >= m) return 0;
if (h < n) return 1 + solve(n, m, 2 * h, w);
return 1 + solve(n, m, h, 2 * w); // w < m
}
The main part of the program. Read the input data.
scanf("%lld %lld %lld %lld", &n, &m, &h, &w);
Compute and print the answer.
printf("%lld\n", min(solve(n, m, h, w), solve(m, n,
h, w)));
Python realization
The solve(n,
m, h, w) function solves the problem for a sheet with
dimensions n and m, and an envelope with dimensions h and w.
def solve(n, m, h, w):
if
h >= n and w >= m:
return
0
if
h < n:
return
1 + solve(n, m, h * 2, w)
return
1 + solve(n, m, h, w * 2)
The main part of the program. Read the input data.
n, m, h, w = map(int, input().split())
Compute and print the answer.
res = min(solve(n, m, h, w), solve(m, n, h, w))
print(res)